package com.example.demo.collections;

import java.util.Scanner;

//二叉树系统
public class BinarySystem {
	public static void main(String[] args) {
		BinaryDomain root = null; // 定义头结点
		new BinaryAction().manage(root);
	}
}

class BinaryDomain {
	private int value; // 二叉树值
	BinaryDomain left; // 左结点
	BinaryDomain right; // 右结点

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public BinaryDomain() {
		super();
		// TODO Auto-generated constructor stub
	}

	public BinaryDomain(int value) {
		super();
		this.value = value;
	}
}

interface BinaryBean {
	public void manage(BinaryDomain root); // 二叉树管理

	public BinaryDomain add(BinaryDomain root); // 二叉树增加

	public BinaryDomain delete(BinaryDomain root); // 二叉树删除

	public void query(BinaryDomain root); // 二叉树查询

	public void update(BinaryDomain root); // 二叉树修改
}

class BinaryAction implements BinaryBean {

	private Scanner input = new Scanner(System.in);

	@Override
	public void manage(BinaryDomain root) {
		while (true) {
			System.out.println("①增加   ②删除   ③查询   ④修改   ⑤返回");
			int select = input.nextInt();
			if (select == 1) {
				root = add(root);
			} else if (select == 2) {
				root = delete(root);
			} else if (select == 3) {
				query(root);
			} else if (select == 4) {
				update(root);
			} else {
				break;
			}
		}
	}

	// 增加
	@Override
	public BinaryDomain add(BinaryDomain root) {
		System.out.println("请输入需要增加的值: ");
		int value = input.nextInt();
		if (value < 0) {
			System.out.println("输入的值不合法");
		} else {
			BinaryDomain binary = new BinaryDomain(value); // 将值存入对象
			if (root == null) { // 头为空
				root = binary; // 将值给头
				System.out.println("二叉树的头结点增加成功");
			} else {
				BinaryDomain temp = root; // 将头保护起来
				while (temp != null) {
					// 小左大右
					if (binary.getValue() > temp.getValue()) {
						// 要增加的值大于当前头的值
						if (temp.right == null) {
							temp.right = binary;
							System.out.println("添加右子树值成功");
							break;
						} else {
							temp = temp.right;
						}
					} else if (binary.getValue() < temp.getValue()) {
						// 要增加的值小于当前头的值
						if (temp.left == null) {
							temp.left = binary;
							System.out.println("添加左子树值成功");
							break;
						} else {
							temp = temp.left;
						}
					} else {
						// 要增加的值等于当前头的值
						System.out.println("要增加的数值已存在，增加数据失败");
						break;
					}
				}
			}
		}
		return root;
	}

	// 删除
	@Override
	public BinaryDomain delete(BinaryDomain root) {
		BinaryDomain temp = root; // 保护头结点
		BinaryDomain tempPre = null; // 要删除的前一个结点
		BinaryDomain del = null; // 记录要删除的结点
		System.out.println("请输入需要删除的值: ");
		int value = input.nextInt();
		while (temp != null) {
			if (temp.getValue() == value) {
				// 当前结点值 == 要删除的值
				del = temp; // 记录要删除的结点
				break;
			} else if (temp.getValue() > value) {
				// 当前结点值 > 要删除的值 往左移至下一个
				tempPre = temp; // 记录要删除结点的前一个结点
				temp = temp.left;
			} else {
				// 当前结点值 < 要删除的值 往右移至下一个
				tempPre = temp;
				temp = temp.right;
			}
		}
		// 判断要删除的结点是否为头结点
		if (del != null && tempPre == null) {
			System.out.println("要删除的为头结点");
			if (del.left == null && del.right == null) {
				// 头结点 无左无右
				root = null;
				System.out.println("删除 无左无右 头结点成功");
			} else if (del.left != null && del.right == null) {
				// 要删除的头结点 有左无右
				root = del.left;
				System.out.println("删除 有左无右 头结点成功");
			} else if (del.left == null && del.right != null) {
				// 要删除的头结点 无左有右
				root = del.right;
				System.out.println("删除 无左有右 头结点成功");
			} else {
				// 要删除的头结点 有左有右
				System.out.println("要删除的头结点有左有右: ①上移左边的最右边结点值   ②上移右边的最左边结点值");
				int option = input.nextInt();
				if (option == 1) {
					// 移左边的最右边结点的值
					BinaryDomain delLeft = del.left; // 用一个对象指向要删除结点的左边
					if (delLeft.right == null && delLeft.left == null) {
						// 如果要删除的结点的左边结点没有子结点，则把要删除的结点值等于delLeft值，需要删除结点的左结点为空
						del.setValue(delLeft.getValue());
						del.left = null;
						System.out.println("删除 有左有右 头结点成功，头结点的左子树下 无子树");
					} else if (delLeft.right == null && delLeft.left != null) {
						// 要删除的结点的左边结点 有左子树无右子树
						del.setValue(delLeft.getValue());
						del.left = delLeft.left;
						System.out.println("删除 有左有右 头结点成功，头结点的左子树下 有左子树无右子树");
					} else {
						// 要删除的结点的左边结点有右子树
						BinaryDomain movePre = null; // 记录删除结点左边结点的需要移走的最右边的结点的父结点
						while (delLeft.right != null) {
							movePre = delLeft;
							delLeft = delLeft.right;
						}
						del.setValue(delLeft.getValue());
						movePre.right = delLeft.left;
						System.out.println("删除 有左有右 头结点成功，头结点的左子树下 有右子树 需要移动");
					}
				} else {
					// 移右边的最左边结点值
					BinaryDomain delRight = del.right; // 用一个对象指向要删除结点的右边
					if (delRight.right == null && delRight.left == null) {
						// 如果要删除的结点的右边结点没有子结点，则把要删除的结点值等于delRight值，需要删除结点的右结点为空
						del.setValue(delRight.getValue());
						del.right = null;
						System.out.println("删除 有左有右 头结点成功，头结点的右子树下 无子树");
					} else if (delRight.right != null && delRight.left == null) {
						// 要删除的结点的右边结点 有右子树无左子树
						del.setValue(delRight.getValue());
						del.right = delRight.right;
						System.out.println("删除 有左有右 头结点成功，头结点的右子树下 有右子树无左子树");
					} else {
						// 要删除的结点的右边结点有左子树
						BinaryDomain movePre = null; // 记录删除结点右边结点的需要移走的最左边的结点的父结点
						while (delRight.left != null) {
							movePre = delRight;
							delRight = delRight.left;
							System.out.println("删除 有左有右 头结点成功，头结点的右子树下 有左子树 需要移动");
						}
					}
				}
			}
		} else {
			// 要删除的不是头结点
			if (del.left == null && del.right == null) {
				// 要删除的结点无左无右 为叶子结点
				System.out.println("需要删除的为叶子结点");
				if (del.getValue() > tempPre.getValue()) {
					// 要删除的值大于父结点的值 删除的为右叶子结点
					tempPre.right = null;
					System.out.println("删除非根结点下的右叶子结点成功");
				} else {
					// 要删除的值小于父结点的值 删除的为左叶子结点
					temp.left = null;
					System.out.println("删除非根结点下的左叶子结点成功");
				}
			} else if (del.left == null && del.right != null) {
				// 要删除的结点无左有右
				if (del.getValue() > tempPre.getValue()) {
					// 要删除的值大于父结点的值 要删除的为父结点下的右子树
					tempPre.right = del.right;
					System.out.println("删除非根结点下的右子树成功，且该右子树下 有右子树无左子树");
				} else {
					// 要删除的值小于父结点的值 要删除的为父结点下的左子树
					tempPre.left = del.right;
					System.out.println("删除非根结点下的左子树成功，且该左子树下 有右子树无左子树");
				}
			} else if (del.left != null && del.right == null) {
				// 要删除的结点有左无右
				if (del.getValue() > tempPre.getValue()) {
					// 要删除的值大于父结点的值 要删除的为父结点下的右子树
					tempPre.right = del.left;
					System.out.println("删除非根结点下的右子树成功，且该右子树下 有左子树无右子树");
				} else {
					// 要删除的值小于父结点的值 要删除的为父结点下的左子树
					tempPre.left = del.left;
					System.out.println("删除非根结点下的左子树成功，且该左子树下 有左子树无右子树");
				}
			} else {
				// 要删除的结点有左有右
				System.out.println("要删除的结点有左有右: ①上移左边的最右边结点值   ②上移右边的最左边结点值");
				int option = input.nextInt();
				if (option == 1) {
					// 移左边的最右边结点
					BinaryDomain delLeft = del.left; // 定义对象指向要删除结点的左边结点
					if (delLeft.right == null && delLeft.left == null) {
						// 要删除结点的左边结点 无左子树无右子树
						del.setValue(delLeft.getValue());
						del.left = null;
						System.out.println("删除非根结点下左子树成功，且该左子树下 无左子树无右子树");
					} else if (delLeft.right == null && delLeft.left != null) {
						// 要删除结点的左边结点 有左子树无右子树
						del.setValue(delLeft.getValue());
						del.left = delLeft.left;
						System.out.println("删除非根结点下左子树成功，且该左子树下 有左子树无右子树");
					} else {
						// 要删除结点的左边结点 无左子树有右子树
						BinaryDomain movePre = null; // 记录删除结点左边结点的需要移走的最右边的结点的父结点
						while (delLeft.right != null) {
							movePre = delLeft;
							delLeft = delLeft.right;
						}
						del.setValue(delLeft.getValue());
						movePre.right = delLeft.left;
						System.out.println("删除非根结点下左子树成功，且该左子树下 有右子树 需要移动");
					}
				} else {
					// 移右边的最左边结点
					BinaryDomain delRight = del.right; // 定义对象指向要删除结点的右结点
					if (delRight.right == null && delRight.left == null) {
						// 要删除结点的右子树下无子树
						del.setValue(delRight.getValue());
						del.right = null;
						System.out.println("删除非根结点下右子树成功，且该右子树下 无子树");
					} else if (delRight.right != null && delRight.left == null) {
						// 要删除结点的右子树下有右子树无左子树
						del.setValue(delRight.getValue());
						del.right = delRight.right;
						System.out.println("删除非根结点下右子树成功，且该右子树下 无左子树有右子树");
					} else {
						// 要删除结点的右子树下有左子树
						BinaryDomain movePre = null; // 记录删除结点右边结点的需要移走的最左边的结点的父结点
						while (delRight.left != null) {
							movePre = delRight;
							delRight = delRight.left;
						}
						del.setValue(delRight.getValue());
						movePre.left = del.right;
						System.out.println("删除非根结点下右子树成功，且该右子树下 有左子树 需要移动");
					}
				}
			}
		}
		return root;
	}

	// 查询
	@Override
	public void query(BinaryDomain root) {
		System.out.println("①先序查询   ②中序查询   ③后序查询");
		int select = input.nextInt();
		if (select == 1) {
			// 先序查询 根 左 右
			preorder(root);
		} else if (select == 2) {
			// 中序查询 左 根 右
			inorder(root);
		} else {
			// 后序查询 左 右 根
			epilogue(root);
		}
	}

	// 先序查询 根 左 右
	public void preorder(BinaryDomain root) {
		BinaryDomain temp = root;
		if (temp != null) {
			System.out.println("先序查询为: " + temp.getValue()); // 根
			preorder(temp.left); // 左
			preorder(temp.right); // 右
		}
	}

	// 中序查询 左 根 右
	public void inorder(BinaryDomain root) {
		BinaryDomain temp = root;
		if (temp != null) {
			inorder(temp.left); // 左
			System.out.println("中序查询为: " + temp.getValue()); // 根
			inorder(temp.right); // 右
		}
	}

	// 后序查询 左 右 根
	public void epilogue(BinaryDomain root) {
		BinaryDomain temp = root;
		if (temp != null) {
			epilogue(temp.left); // 左
			epilogue(temp.right); // 右
			System.out.println("后序查询为: " + temp.getValue()); // 根
		}
	}

	// 修改
	@Override
	public void update(BinaryDomain root) {
		System.out.println("请输入需要修改的数据元素: ");
		int update = input.nextInt();
	}
}
